package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 101. 对称二叉树
 * https://leetcode.cn/problems/symmetric-tree/description/
 */
public class LC101_SymmetricTree {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            return root == null || isSymmetric0(root.left, root.right);
        }

        public boolean isSymmetric0(TreeNode left, TreeNode right) {
            if (left == null && right == null) return true;
            if (left == null || right == null || left.val != right.val) return false;
            return isSymmetric0(left.left, right.right) && isSymmetric0(left.right, right.left);
        }
    }

    /**
     * 本质上为左子树的左子树与右子树的右子树是否一样；左子树的右子树是否与右子树的左子树
     * 这是与LC100的不同
     */
    @XOptimal
    class Solution1 {
        public boolean isSymmetric(TreeNode root) {
            return isSameTree(root.left, root.right);
        }

        private boolean isSameTree(TreeNode left, TreeNode right) {
            if (left == null || right == null) return left == right;
            return left.val == right.val && isSameTree(left.left, right.right) && isSameTree(left.right, right.left);
        }
    }
}
